import copy


def get_neighbour_lives(i, j, cells):
    diffs = [[-1, -1], [-1, 0], [-1, 1],
             [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
    lives = 0
    for d in diffs:
        row, col = i+d[0], j+d[1]
        if row > -1 and row < len(cells) and col > -1 and col < len(cells[0]):
            if cells[row][col]:
                lives += 1
    return lives


def expand(cells, d=10):
    out = []
    for i in range(d):
        out.append([0 for i in range(2*d+len(cells[0]))])
    for i in range(len(cells)):
        temp = [0 for j in range(d)]
        row = copy.deepcopy(temp)
        row.extend(cells[i])
        row.extend(temp)
        out.append(row)
    for i in range(d):
        out.append([0 for i in range(2*d+len(cells[0]))])
    return out


def cut_deadborder(cells):
    begin_idx, end_idx = 0, len(cells)-1
    for i in range(len(cells)):
        if(sum(cells[i])):
            begin_idx = i
            break
    for i in range(len(cells)-1, -1, -1):
        if(sum(cells[i])):
            end_idx = i
            break
    cells = copy.deepcopy(cells[begin_idx:end_idx+1])
    begin_idx, end_idx = 0, len(cells[0])-1
    for j in range(len(cells[0])):
        if sum(x[j] for x in cells):
            begin_idx = j
            break
    for j in range(len(cells[0])-1, -1, -1):
        if sum(x[j] for x in cells):
            end_idx = j
            break
    return [x[begin_idx:end_idx+1] for x in cells]


def get_generation(input, generations):
    cells = expand(copy.deepcopy(input))
    for t in range(generations):
        copys = copy.deepcopy(cells)
        for i in range(len(cells)):
            for j in range(len(cells[0])):
                lives = get_neighbour_lives(i, j, cells)
                if copys[i][j]:
                    if lives < 2 or lives > 3:
                        copys[i][j] = 0
                else:
                    if lives == 3:
                        copys[i][j] = 1
        cells = copy.deepcopy(copys)
    return cut_deadborder(cells)
